

<!DOCTYPE html>
<html lang="zh-CN" data-default-color-scheme=auto>



<head>
  <meta charset="UTF-8">
  <link rel="apple-touch-icon" sizes="76x76" href="/img/favicon.png">
  <link rel="icon" href="/img/favicon.png">
  <meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=5.0, shrink-to-fit=no">
  <meta http-equiv="x-ua-compatible" content="ie=edge">
  
  <meta name="theme-color" content="#2f4154">
  <meta name="author" content="Cai Shibo">
  <meta name="keywords" content="cc">
  
    <meta name="description" content="该文章记录对 其他算法 相关题目的分析理解。">
<meta property="og:type" content="article">
<meta property="og:title" content="算法 --- 其他算法">
<meta property="og:url" content="https://hahsx_xd.gitee.io/2022/03/21/%E7%AE%97%E6%B3%95-%E5%85%B6%E4%BB%96%E7%AE%97%E6%B3%95/index.html">
<meta property="og:site_name" content="🍊CAI SHIBO🥬">
<meta property="og:description" content="该文章记录对 其他算法 相关题目的分析理解。">
<meta property="og:locale" content="zh_CN">
<meta property="og:image" content="https://hahsx_xd.gitee.io/images/pasted-54.png">
<meta property="article:published_time" content="2022-03-21T09:17:00.000Z">
<meta property="article:modified_time" content="2022-11-29T07:14:46.511Z">
<meta property="article:author" content="Cai Shibo">
<meta property="article:tag" content="其他算法">
<meta name="twitter:card" content="summary_large_image">
<meta name="twitter:image" content="https://hahsx_xd.gitee.io/images/pasted-54.png">
  
  
  <title>算法 --- 其他算法 - 🍊CAI SHIBO🥬</title>

  <link  rel="stylesheet" href="https://cdn.jsdelivr.net/npm/bootstrap@4/dist/css/bootstrap.min.css" />


  <link  rel="stylesheet" href="https://cdn.jsdelivr.net/npm/github-markdown-css@4/github-markdown.min.css" />
  <link  rel="stylesheet" href="https://cdn.jsdelivr.net/npm/hint.css@2/hint.min.css" />

  
    
    
      
      <link  rel="stylesheet" href="https://cdn.jsdelivr.net/npm/highlight.js@10/styles/github-gist.min.css" />
    
  

  
    <link  rel="stylesheet" href="https://cdn.jsdelivr.net/npm/@fancyapps/fancybox@3/dist/jquery.fancybox.min.css" />
  


<!-- 主题依赖的图标库，不要自行修改 -->

<link rel="stylesheet" href="//at.alicdn.com/t/font_1749284_ba1fz6golrf.css">



<link rel="stylesheet" href="//at.alicdn.com/t/font_1736178_lbnruvf0jn.css">


<link  rel="stylesheet" href="/css/main.css" />

<!-- 自定义样式保持在最底部 -->


  <script id="fluid-configs">
    var Fluid = window.Fluid || {};
    var CONFIG = {"hostname":"hahsx_xd.gitee.io","root":"/","version":"1.8.14","typing":{"enable":true,"typeSpeed":70,"cursorChar":".|","loop":false},"anchorjs":{"enable":true,"element":"h1,h2,h3,h4,h5,h6","placement":"right","visible":"hover","icon":"#"},"progressbar":{"enable":true,"height_px":3,"color":"#29d","options":{"showSpinner":false,"trickleSpeed":100}},"copy_btn":true,"image_zoom":{"enable":true,"img_url_replace":["",""]},"toc":{"enable":true,"headingSelector":"h1,h2,h3,h4,h5,h6","collapseDepth":5},"lazyload":{"enable":true,"loading_img":"/img/loading.gif","onlypost":true,"offset_factor":2},"web_analytics":{"enable":false,"baidu":null,"google":null,"gtag":null,"tencent":{"sid":null,"cid":null},"woyaola":null,"cnzz":null,"leancloud":{"app_id":null,"app_key":null,"server_url":null,"path":"window.location.pathname","ignore_local":false}},"search_path":"/local-search.xml"};
  </script>
  <script  src="/js/utils.js" ></script>
  <script  src="/js/color-schema.js" ></script>
<meta name="generator" content="Hexo 5.4.0"><link rel="alternate" href="/atom.xml" title="🍊CAI SHIBO🥬" type="application/atom+xml">
</head>


<body>
  <header style="height: 70vh;">
    <nav id="navbar" class="navbar fixed-top  navbar-expand-lg navbar-dark scrolling-navbar">
  <div class="container">
    <a class="navbar-brand" href="/">
      <strong>^_^ 🥬 CC</strong>
    </a>

    <button id="navbar-toggler-btn" class="navbar-toggler" type="button" data-toggle="collapse"
            data-target="#navbarSupportedContent"
            aria-controls="navbarSupportedContent" aria-expanded="false" aria-label="Toggle navigation">
      <div class="animated-icon"><span></span><span></span><span></span></div>
    </button>

    <!-- Collapsible content -->
    <div class="collapse navbar-collapse" id="navbarSupportedContent">
      <ul class="navbar-nav ml-auto text-center">
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/">
                <i class="iconfont icon-home-fill"></i>
                首页
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/archives/">
                <i class="iconfont icon-archive-fill"></i>
                归档
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/categories/">
                <i class="iconfont icon-category-fill"></i>
                分类
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/tags/">
                <i class="iconfont icon-tags-fill"></i>
                标签
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/about/">
                <i class="iconfont icon-user-fill"></i>
                关于
              </a>
            </li>
          
        
        
          <li class="nav-item" id="search-btn">
            <a class="nav-link" target="_self" href="javascript:;" data-toggle="modal" data-target="#modalSearch" aria-label="Search">
              &nbsp;<i class="iconfont icon-search"></i>&nbsp;
            </a>
          </li>
        
        
          <li class="nav-item" id="color-toggle-btn">
            <a class="nav-link" target="_self" href="javascript:;" aria-label="Color Toggle">&nbsp;<i
                class="iconfont icon-dark" id="color-toggle-icon"></i>&nbsp;</a>
          </li>
        
      </ul>
    </div>
  </div>
</nav>

    <div class="banner" id="banner" parallax=true
         style="background: url('/img/default.png') no-repeat center center;
           background-size: cover;">
      <div class="full-bg-img">
        <div class="mask flex-center" style="background-color: rgba(0, 0, 0, 0.3)">
          <div class="page-header text-center fade-in-up">
            <span class="h2" id="subtitle" title="算法 --- 其他算法">
              
            </span>

            
              <div class="mt-3">
  
    <span class="post-meta mr-2">
      <i class="iconfont icon-author" aria-hidden="true"></i>
      Cai Shibo
    </span>
  
  
    <span class="post-meta">
      <i class="iconfont icon-date-fill" aria-hidden="true"></i>
      <time datetime="2022-03-21 17:17" pubdate>
        2022年3月21日 下午
      </time>
    </span>
  
</div>

<div class="mt-1">
  
    <span class="post-meta mr-2">
      <i class="iconfont icon-chart"></i>
      9.8k 字
    </span>
  

  
    <span class="post-meta mr-2">
      <i class="iconfont icon-clock-fill"></i>
      
      
      49 分钟
    </span>
  

  
  
    
      <!-- 不蒜子统计文章PV -->
      <span id="busuanzi_container_page_pv" style="display: none">
        <i class="iconfont icon-eye" aria-hidden="true"></i>
        <span id="busuanzi_value_page_pv"></span> 次
      </span>
    
  
</div>

            
          </div>

          
        </div>
      </div>
    </div>
  </header>

  <main>
    
      

<div class="container-fluid nopadding-x">
  <div class="row nomargin-x">
    <div class="d-none d-lg-block col-lg-2"></div>
    <div class="col-lg-8 nopadding-x-md">
      <div class="container nopadding-x-md" id="board-ctn">
        <div class="py-5" id="board">
          <article class="post-content mx-auto">
            <!-- SEO header -->
            <h1 style="display: none">算法 --- 其他算法</h1>
            
              <p class="note note-info">
                
                  最后更新：23 天前
                
              </p>
            
            <div class="markdown-body">
              <p><strong>该文章记录对 其他算法 相关题目的分析理解。</strong></p>
<span id="more"></span>

<hr>
<h4 id="JZ66-构建乘积数组-E"><a href="#JZ66-构建乘积数组-E" class="headerlink" title="JZ66 构建乘积数组 E"></a>JZ66 构建乘积数组 E</h4><p>描述：给定一个数组 A[0,1,…,n-1] ,请构建一个数组 B[0,1,…,n-1] ,其中 B 的元素 B[i]=A[0]*A[1]*…*A[i-1]*A[i+1]*…*A[n-1]（除 A[i] 以外的全部元素的的乘积）。程序中不能使用除法。（注意：规定 B[0] = A[1] * A[2] * … * A[n-1]，B[n-1] = A[0] * A[1] * … * A[n-2]）</p>
<p>解：暴力解法，时间复杂度为O(n^2)。<br>从下图发现：<strong>B[i]=左边红色部分A[i]乘积*1*右边次色部分A[i]乘积</strong><br><img src="/images/pasted-54.png" srcset="/img/loading.gif" lazyload alt="upload successful"></p>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-keyword">import</span> java.util.ArrayList;<br><br><span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span> </span>&#123;<br>    <span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span>[] multiply(<span class="hljs-keyword">int</span>[] A) &#123;<br>        <span class="hljs-keyword">int</span>[] B = <span class="hljs-keyword">new</span> <span class="hljs-keyword">int</span>[A.length];<br>        B[<span class="hljs-number">0</span>] = <span class="hljs-number">1</span>;<br>        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">1</span>; i &lt; A.length; ++i) &#123;<br>            <span class="hljs-comment">//左边红色部分乘积</span><br>            B[i] = A[(i - <span class="hljs-number">1</span>)] * B[i - <span class="hljs-number">1</span>];<br>        &#125;<br>        <span class="hljs-comment">//temp用来存储紫色部分的乘积</span><br>        <span class="hljs-keyword">int</span> temp = <span class="hljs-number">1</span>;<br>        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = A.length - <span class="hljs-number">2</span>; i &gt;= <span class="hljs-number">0</span>; --i) &#123;<br>            <span class="hljs-comment">//右边紫色部分乘积</span><br>            temp = temp * A[i + <span class="hljs-number">1</span>];<br>            <span class="hljs-comment">//乘到对应的B[i]上</span><br>            B[i] = B[i] * temp;<br>        &#125;<br>        <span class="hljs-keyword">return</span> B;<br>    &#125;<br>&#125;<br></code></pre></div></td></tr></table></figure>
<hr>
<h4 id="JZ81-调整数组顺序使奇数位于偶数前面（二）E"><a href="#JZ81-调整数组顺序使奇数位于偶数前面（二）E" class="headerlink" title="JZ81 调整数组顺序使奇数位于偶数前面（二）E"></a>JZ81 调整数组顺序使奇数位于偶数前面（二）E</h4><p>描述：输入一个长度为 n 整数数组，数组里面可能含有相同的元素，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前面部分，所有的偶数位于数组的后面部分，对奇数和奇数，偶数和偶数之间的相对位置不做要求，但是时间复杂度和空间复杂度必须如下要求：**时间复杂O(n)，空间复杂度O(1)**。</p>
<p>解：使用LinkedList链表，for循环遍历输入数组；奇数addFirst(),偶数addLast()。<br>时间复杂度为O(n)，空间复杂度为O(n) – LinkedList使用。  </p>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-keyword">import</span> java.util.*;<br><br><span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span> </span>&#123;<br>    <span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span>[] reOrderArrayTwo(<span class="hljs-keyword">int</span>[] array) &#123;<br>        <span class="hljs-comment">// write code here</span><br>        LinkedList&lt;Integer&gt; list = <span class="hljs-keyword">new</span> LinkedList&lt;&gt;();<br>        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i : array) &#123;<br>            <span class="hljs-keyword">if</span> (i % <span class="hljs-number">2</span> == <span class="hljs-number">1</span>) &#123;<br>                list.addFirst(i);<br>            &#125; <span class="hljs-keyword">else</span> &#123;<br>                list.addLast(i);<br>            &#125;<br>        &#125;<br>        <span class="hljs-keyword">int</span> n = list.size();<br>        <span class="hljs-keyword">int</span>[] ints = <span class="hljs-keyword">new</span> <span class="hljs-keyword">int</span>[n];<br>        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt; n; ++i) &#123;<br>            ints[i] = list.poll();<br>        &#125;<br>        <span class="hljs-keyword">return</span> ints;<br>    &#125;<br>&#125;<br></code></pre></div></td></tr></table></figure>
<p><strong>优化：</strong>使空间复杂度为O(1)。</p>
<ol>
<li>用两个int模拟指针指向数组最左边和最右边，while (左 &lt; 右)；</li>
<li>左边指针没遇到偶数就向右移动（++），遇到偶数就停止；</li>
<li>右边指针开始移动，没遇到奇数就向左移动（–），遇到奇数就停止；</li>
<li>两个指针交换指向的元素，继续上述操作。</li>
</ol>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-keyword">import</span> java.util.*;<br><br><span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span> </span>&#123;<br>    <span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span>[] reOrderArrayTwo (<span class="hljs-keyword">int</span>[] array) &#123;<br>        <span class="hljs-comment">// write code here</span><br>        <span class="hljs-keyword">int</span> low = <span class="hljs-number">0</span>, high = array.length - <span class="hljs-number">1</span>;<br>        <span class="hljs-keyword">while</span> (low &lt; high) &#123;<br>            <span class="hljs-comment">//同时要满足low &lt; high, 防止输入[1, 3, 5],出现越界的情况</span><br>            <span class="hljs-keyword">while</span> (array[low] % <span class="hljs-number">2</span> == <span class="hljs-number">1</span> &amp;&amp; low &lt; high) &#123;<br>                low ++;<br>            &#125;<br>            <span class="hljs-keyword">while</span> (array[high] % <span class="hljs-number">2</span> == <span class="hljs-number">0</span> &amp;&amp; low &lt; high) &#123;<br>                high --;<br>            &#125;<br>            <span class="hljs-keyword">int</span> temp = array[low];<br>            array[low] = array[high];<br>            array[high] = temp;<br>        &#125;<br>        <span class="hljs-keyword">return</span> array;<br>    &#125;<br>&#125;<br></code></pre></div></td></tr></table></figure>

<hr>
<h4 id="LC03-无重复字符的最长子串-M"><a href="#LC03-无重复字符的最长子串-M" class="headerlink" title="LC03 无重复字符的最长子串 M"></a>LC03 无重复字符的最长子串 M</h4><p>描述：给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。</p>
<p>解：<strong>滑动窗口。</strong></p>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-keyword">import</span> java.util.*;<br><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span> </span>&#123;<br>    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">lengthOfLongestSubstring</span><span class="hljs-params">(String s)</span> </span>&#123;<br>        <span class="hljs-keyword">if</span> (s.length() == <span class="hljs-number">0</span>) &#123;<br>            <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;<br>        &#125;<br>        Set&lt;Character&gt; set = <span class="hljs-keyword">new</span> HashSet&lt;&gt;();<br>        <span class="hljs-keyword">char</span>[] cs = s.toCharArray();<br>        <span class="hljs-keyword">int</span> max = <span class="hljs-number">1</span>, count = <span class="hljs-number">1</span>;<br>        set.add(cs[<span class="hljs-number">0</span>]);<br>        <span class="hljs-keyword">int</span> start = <span class="hljs-number">0</span>, end = <span class="hljs-number">1</span>;<br>        <span class="hljs-keyword">while</span> (end &lt; cs.length) &#123;<br>            <span class="hljs-keyword">if</span> (set.add(cs[end])) &#123;<br>                count ++;<br>                <span class="hljs-keyword">if</span> (count &gt; max) &#123;<br>                    max = count;<br>                &#125;<br>                end ++;<br>            &#125; <span class="hljs-keyword">else</span> &#123;<br>                set.remove(cs[start]);<br>                start ++;<br>                count --;<br>            &#125;<br>        &#125;<br>    <span class="hljs-keyword">return</span> max;<br>    &#125;<br>&#125;<br></code></pre></div></td></tr></table></figure>

<p><strong>优化：</strong>左指针并不需要依次递增，即多了很多无谓的循环。发现有重复字符时，可以直接把左指针移动到第一个重复字符的下一个位置即可。</p>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-keyword">import</span> java.util.*;<br><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span> </span>&#123;<br>    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">lengthOfLongestSubstring</span><span class="hljs-params">(String s)</span> </span>&#123;<br>        <span class="hljs-keyword">if</span> (s.length() == <span class="hljs-number">0</span>) &#123;<br>            <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;<br>        &#125;<br>        HashMap&lt;Character, Integer&gt; map = <span class="hljs-keyword">new</span> HashMap&lt;&gt;();<br>        <span class="hljs-keyword">char</span>[] cs = s.toCharArray();<br>        <span class="hljs-keyword">int</span> max = <span class="hljs-number">1</span>, count = <span class="hljs-number">1</span>;<br>        map.put(cs[<span class="hljs-number">0</span>], <span class="hljs-number">0</span>);<br>        <span class="hljs-keyword">int</span> start = <span class="hljs-number">0</span>, end = <span class="hljs-number">1</span>;<br>        <span class="hljs-keyword">while</span> (end &lt; cs.length) &#123;<br>            <span class="hljs-keyword">if</span> (map.containsKey(cs[end]) &amp;&amp; map.get(cs[end]) &gt;= start) &#123;<br>                start = map.get(cs[end]) + <span class="hljs-number">1</span>;<br>                count = end - start;<br>            &#125;<br>            map.put(cs[end], end);<br>            end ++;<br>            count ++;<br>            max = Math.max(count, max);<br>        &#125;<br>    <span class="hljs-keyword">return</span> max;<br>    &#125;<br>&#125;<br></code></pre></div></td></tr></table></figure>

<hr>
<h4 id="LC05-最长回文子串-M"><a href="#LC05-最长回文子串-M" class="headerlink" title="LC05 最长回文子串 M"></a>LC05 最长回文子串 M</h4><p>描述：给你一个字符串 s，找到 s 中最长的回文子串。</p>
<p>解：<strong>动态规划</strong>，时间复杂度O (n^2)，空间复杂度O (n^2)。  </p>
<ol>
<li>boolean dp [l] [r]，l、r分别表示子字符串开始结束的位置，表示当前子字符串是否为回文。赋值dp [i] [i] = true，对每个字符自己本身一定是回文；</li>
<li>子字符串长度从 2 到 s.length() 遍历;</li>
<li>如果l，r两个字符相同；判断r - l &lt; 3，则l、r中间有0或1个字符，那么一定是回文；如果 &gt; 3，则与dp [l + 1] [r - 1]的值相同。</li>
<li>如果l、r两个字符不相同，则dp [l] [r]为false。</li>
<li>更新记录最长回文的起始位置和长度。</li>
</ol>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span> </span>&#123;<br>    <span class="hljs-function"><span class="hljs-keyword">public</span> String <span class="hljs-title">longestPalindrome</span><span class="hljs-params">(String s)</span> </span>&#123;<br>        <span class="hljs-keyword">int</span> n = s.length();<br>        <span class="hljs-keyword">if</span> (n == <span class="hljs-number">1</span>) &#123;<br>            <span class="hljs-keyword">return</span> s;<br>        &#125;<br>        <span class="hljs-keyword">boolean</span>[][] dp = <span class="hljs-keyword">new</span> <span class="hljs-keyword">boolean</span>[n][n];<br>        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt; n; ++i) &#123;<br>            dp[i][i] = <span class="hljs-keyword">true</span>;<br>        &#125;<br>        <span class="hljs-keyword">int</span> start = <span class="hljs-number">0</span>, maxL = <span class="hljs-number">1</span>;<br>        <span class="hljs-comment">//枚举子串长度</span><br>        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> L = <span class="hljs-number">2</span>; L &lt;= n; ++L) &#123;<br>            <span class="hljs-comment">//起始节点遍历</span><br>            <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> left = <span class="hljs-number">0</span>; left &lt; n; ++left) &#123;<br>                <span class="hljs-comment">//确定结束节点</span><br>                <span class="hljs-keyword">int</span> right = L + left - <span class="hljs-number">1</span>;<br>                <span class="hljs-keyword">if</span> (right &gt;= n) &#123;<br>                    <span class="hljs-keyword">break</span>;<br>                &#125;<br>                <span class="hljs-keyword">if</span> (s.charAt(left) == s.charAt(right)) &#123;<br>                    <span class="hljs-keyword">if</span> (right - left &lt;= <span class="hljs-number">2</span>) &#123;<br>                        <span class="hljs-comment">//如果左右节点中间没有或只有一个字符，只要左右节点相同，一定是回文</span><br>                        dp[left][right] = <span class="hljs-keyword">true</span>;<br>                    &#125; <span class="hljs-keyword">else</span> &#123;<br>                        <span class="hljs-comment">//否则就要根据内部是不是回文来决定</span><br>                        dp[left][right] = dp[left + <span class="hljs-number">1</span>][right - <span class="hljs-number">1</span>];<br>                    &#125;<br>                &#125; <span class="hljs-keyword">else</span> &#123;<br>                    dp[left][right] = <span class="hljs-keyword">false</span>;<br>                &#125;<br>                <span class="hljs-comment">//判断是否为更长的回文</span><br>                <span class="hljs-keyword">if</span> (L &gt; maxL &amp;&amp; dp[left][right]) &#123;<br>                    start = left;<br>                    maxL = L;<br>                &#125;<br>            &#125;<br>        &#125;<br>        <span class="hljs-keyword">return</span> s.substring(start, start + maxL);<br>    &#125;<br>&#125;<br></code></pre></div></td></tr></table></figure>

<p><strong>优化：中心对称算法</strong>，时间复杂度O (n^2)，空间复杂度O (1)。<br>遍历字符串每个中心，将其向左右两边同时延伸，直至遇到左右两个字符不相等，记录长度。<br>这里有两种情况：1、l = r = i，表示奇数长度的子字符串；2、l = i；r = i + 1，表示偶数长度的子字符串。  </p>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span> </span>&#123;<br>    <span class="hljs-function"><span class="hljs-keyword">public</span> String <span class="hljs-title">longestPalindrome</span><span class="hljs-params">(String s)</span> </span>&#123;<br>        <span class="hljs-keyword">int</span> n = s.length ();<br>        <span class="hljs-keyword">if</span> (n == <span class="hljs-number">1</span>) &#123;<br>            <span class="hljs-keyword">return</span> s;<br>        &#125;<br>        <span class="hljs-keyword">int</span> maxL = <span class="hljs-number">1</span>, start = <span class="hljs-number">0</span>;<br>        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt; n; ++i) &#123;<br>            <span class="hljs-keyword">int</span> nm = findMax(s, i, i);<br>            <span class="hljs-keyword">if</span> (nm &gt; maxL) &#123;<br>                maxL = nm;<br>                start = i - (maxL - <span class="hljs-number">1</span>) / <span class="hljs-number">2</span>;<br>            &#125;<br>            nm = findMax(s, i, i + <span class="hljs-number">1</span>);<br>            <span class="hljs-keyword">if</span> (nm &gt; maxL) &#123;<br>                maxL = nm;<br>                start = i - (maxL - <span class="hljs-number">2</span>) / <span class="hljs-number">2</span>;<br>            &#125;<br>        &#125;<br>        <span class="hljs-keyword">return</span> s.substring(start, maxL + start);<br>    &#125;<br><br>    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">findMax</span><span class="hljs-params">(String s, <span class="hljs-keyword">int</span> l, <span class="hljs-keyword">int</span> r)</span> </span>&#123;<br>        <span class="hljs-keyword">if</span> (l == r) &#123;<br>                l--;<br>                r++;<br>        &#125;<br>        <span class="hljs-keyword">while</span> (l &gt;= <span class="hljs-number">0</span> &amp;&amp; r &lt; s.length()) &#123;<br>            <span class="hljs-keyword">if</span> (s.charAt(l) == s.charAt(r)) &#123;<br>                l--;<br>                r++;<br>            &#125; <span class="hljs-keyword">else</span> &#123;<br>                <span class="hljs-keyword">break</span>;<br>            &#125;<br>        &#125;<br>        <span class="hljs-keyword">return</span> r - l + <span class="hljs-number">1</span> - <span class="hljs-number">2</span>;<br>    &#125;<br><br>&#125;<br></code></pre></div></td></tr></table></figure>

<p><strong>再优化：马拉车（Manacher）算法</strong>，时间复杂度O (n)，空间复杂度O (n)。</p>
<hr>
<h4 id="LC396-旋转函数-M"><a href="#LC396-旋转函数-M" class="headerlink" title="LC396 旋转函数 M"></a>LC396 旋转函数 M</h4><p>描述：给定一个长度为 n 的整数数组 nums 。</p>
<p>假设 arrk 是数组 nums 顺时针旋转 k 个位置后的数组，我们定义 nums 的 旋转函数  F 为：<br><code> F(k) = 0 \* arrk [0] + 1 \* arrk [1] + ... + (n - 1) \* arrk [n - 1]</code><br>返回 F(0), F(1), …, F(n-1)中的最大值。</p>
<p>解：寻找规律。以长度为 k 的数组为例</p>
<div class="hljs code-wrapper"><pre><code class="hljs">F（0）    0 * f(0)     1 * f(1)     2 * f(2)     3 * f(3)  
F（1）    3 * f(0)     0 * f(1)     1 * f(2)     2 * f(3)  
F（2）    2 * f(0)     3 * f(1)     0 * f(2)     1 * f(3)  
F（3）    1 * f(0)     2 * f(1)     3 * f(2)     0 * f(3)  
......
</code></pre></div>
<p>不难发现总结<br>F（n）- F（n-1） = k * f（n-1） -（ f（0）+ f（1）+…+ f（k-1）），n &lt; k</p>
<p>即<br>F（n）= F（n-1）+ k * f（n-1） -（ f（0）+ f（1）+…+ f（k-1）），n &lt; k</p>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span> </span>&#123;<br>    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">maxRotateFunction</span><span class="hljs-params">(<span class="hljs-keyword">int</span>[] nums)</span> </span>&#123;<br>        <span class="hljs-keyword">int</span> sum = <span class="hljs-number">0</span>, record = <span class="hljs-number">0</span>;<br>        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt; nums.length; ++i) &#123;<br>            sum += nums[i];<br>            record += i * nums[i];<br>        &#125;<br>        <span class="hljs-keyword">int</span> max = record;<br>        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">1</span>; i &lt; nums.length; ++i) &#123;<br>            record = record - sum + nums.length * nums[i - <span class="hljs-number">1</span>];<br>            max = Math.max(record, max);<br>        &#125;<br>        <span class="hljs-keyword">return</span> max;<br>    &#125;<br>&#125;<br></code></pre></div></td></tr></table></figure>

<hr>
<h4 id="LC398-随机数索引-M"><a href="#LC398-随机数索引-M" class="headerlink" title="LC398 随机数索引 M"></a>LC398 随机数索引 M</h4><p>描述：<br>给定一个可能含有重复元素的整数数组，要求随机输出给定的数字的索引。 您可以假设给定的数字一定存在于数组中。<br>注意：<br>数组大小可能非常大。 使用太多额外空间的解决方案将不会通过测试。</p>
<p>解：</p>
<ul>
<li><p>蓄水池抽样（时间换空间）<br>时间复杂度：初始化的复杂度为O(1)，pick 操作的复杂度为O(n)<br>空间复杂度：O(1)</p>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span> </span>&#123;<br>    <span class="hljs-keyword">int</span>[] nums;<br><br>    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-title">Solution</span><span class="hljs-params">(<span class="hljs-keyword">int</span>[] nums)</span> </span>&#123;<br>        <span class="hljs-keyword">this</span>.nums = nums;<br>    &#125;<br>    <br>    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">pick</span><span class="hljs-params">(<span class="hljs-keyword">int</span> target)</span> </span>&#123;<br>        Random rd = <span class="hljs-keyword">new</span> Random();<br>        <span class="hljs-keyword">int</span> n = <span class="hljs-number">0</span>, result = <span class="hljs-number">0</span>;<br>        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt; nums.length; ++i) &#123;<br>        	<span class="hljs-comment">//与目标数字相同</span><br>            <span class="hljs-keyword">if</span> (target == nums[i]) &#123;<br>                ++n;<br>                <span class="hljs-comment">//如有多个索引，保证每个索引的返回概率相同</span><br>                <span class="hljs-keyword">if</span> (rd.nextInt(n) == <span class="hljs-number">0</span>) &#123;<br>                    result = i;<br>                &#125;<br>            &#125;<br>        &#125;<br>        <span class="hljs-keyword">return</span> result;<br>    &#125;<br>&#125;<br></code></pre></div></td></tr></table></figure></li>
<li><p>HashMap（空间换时间）<br>时间复杂度：初始化的复杂度为O(n)，pick 操作的复杂度为O(1)<br>空间复杂度：O(n)</p>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span> </span>&#123;<br>    HashMap&lt;Integer, ArrayList&lt;Integer&gt;&gt; map = <span class="hljs-keyword">new</span> HashMap&lt;&gt;();<br><br>    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-title">Solution</span><span class="hljs-params">(<span class="hljs-keyword">int</span>[] nums)</span> </span>&#123;<br>        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt; nums.length; ++i) &#123;<br>            <span class="hljs-keyword">if</span> (map.containsKey(nums[i])) &#123;<br>                ArrayList&lt;Integer&gt; list = map.get(nums[i]);<br>                list.add(i);<br>                map.put(nums[i], list);<br>            &#125;<br>            <span class="hljs-keyword">else</span> &#123;<br>                ArrayList&lt;Integer&gt; list = <span class="hljs-keyword">new</span> ArrayList&lt;&gt;();<br>                list.add(i);<br>                map.put(nums[i], list);<br>            &#125;<br>        &#125;<br>    &#125;<br>    <br>    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">pick</span><span class="hljs-params">(<span class="hljs-keyword">int</span> target)</span> </span>&#123;<br>        Random rd = <span class="hljs-keyword">new</span> Random();<br>        <span class="hljs-keyword">int</span> n = rd.nextInt(map.get(target).size());<br>        <span class="hljs-keyword">return</span> map.get(target).get(n);<br>    &#125;<br>&#125;<br></code></pre></div></td></tr></table></figure></li>
</ul>
<hr>
<h4 id="LC587-安装栅栏-H"><a href="#LC587-安装栅栏-H" class="headerlink" title="LC587 安装栅栏 H"></a>LC587 安装栅栏 H</h4><p>描述：在一个二维的花园中，有一些用 (x, y) 坐标表示的树。由于安装费用十分昂贵，你的任务是先用最短的绳子围起所有的树。只有当所有的树都被绳子包围时，花园才能围好栅栏。你需要找到正好位于栅栏边界上的树的坐标。</p>
<p>解：<br>前置知识：两条直线的向量叉乘结果 &gt; 0 时，直线 2 在直线 1 的逆时针位置。  </p>
<p><strong>二维凸包（Andrew 算法）</strong>  </p>
<ol>
<li>将数组按照x升序，（x相同时）y升序的规则排序。</li>
<li>利用 List 模拟栈，数组来记录节点是否使用过。</li>
<li>实现从左到右的部分：<ul>
<li>当总数小于 2，则直接放入 List 中。</li>
<li>总数大于 2，判断当前节点、前节点分别与前前节点连成的直线的叉乘结果：如果结果大于 0，则使用当前节点替换前一节点；否则加入新节点。</li>
<li>如替换节点，则需要判断替换后节点、前节点于前前节点连成的直线的叉乘结果：如结果大于 0，则直接删除前节点，继续该判断；否则离开该判断。</li>
</ul>
</li>
<li>实现从右到左的部分，<strong>过程基本相同，但要注意：</strong><ul>
<li>叉乘结果判断也是大于 0 交换，因为是逆时针的规律。</li>
<li>最后一个节点不需要判断，因为一定在 List 中。</li>
<li>已经被使用的节点，不能再使用。</li>
<li>最后需单独判断首节点，因为其一定被使用，但最后形成环需要连接判断。</li>
</ul>
</li>
</ol>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span> </span>&#123;<br>    <br>    <span class="hljs-comment">//返回叉乘结果</span><br>    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">cross</span><span class="hljs-params">(<span class="hljs-keyword">int</span>[] a, <span class="hljs-keyword">int</span>[] b, <span class="hljs-keyword">int</span>[] c)</span> </span>&#123;<br>        <span class="hljs-keyword">return</span> (b[<span class="hljs-number">0</span>] - a[<span class="hljs-number">0</span>]) * (c[<span class="hljs-number">1</span>] - a[<span class="hljs-number">1</span>]) - (b[<span class="hljs-number">1</span>] - a[<span class="hljs-number">1</span>]) * (c[<span class="hljs-number">0</span>] - a[<span class="hljs-number">0</span>]);<br>    &#125;<br><br>	<span class="hljs-comment">//按照x升序，（x相同时）y升序 排序</span><br>    <span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span>[][] outerTrees(<span class="hljs-keyword">int</span>[][] trees) &#123;<br>        Arrays.sort(trees, <span class="hljs-keyword">new</span> Comparator&lt;<span class="hljs-keyword">int</span>[]&gt;() &#123;<br>            <span class="hljs-meta">@Override</span><br>            <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">compare</span><span class="hljs-params">(<span class="hljs-keyword">int</span>[] o1, <span class="hljs-keyword">int</span>[] o2)</span> </span>&#123;<br>                <span class="hljs-keyword">if</span> (o1[<span class="hljs-number">0</span>] == o2[<span class="hljs-number">0</span>]) &#123;<br>                    <span class="hljs-keyword">return</span> o1[<span class="hljs-number">1</span>] - o2[<span class="hljs-number">1</span>];<br>                &#125;<br>                <span class="hljs-keyword">return</span> o1[<span class="hljs-number">0</span>] - o2[<span class="hljs-number">0</span>];<br>            &#125;<br>        &#125;);<br><br>        List&lt;Integer&gt; list = <span class="hljs-keyword">new</span> ArrayList&lt;&gt;();<br>        <span class="hljs-keyword">boolean</span>[] pd = <span class="hljs-keyword">new</span> <span class="hljs-keyword">boolean</span>[trees.length];<br><br>        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt; trees.length; ++i) &#123;<br>        	<span class="hljs-comment">//首先要有1个节点可以于另一个节点连成线</span><br>            <span class="hljs-keyword">if</span> (list.size() &lt; <span class="hljs-number">2</span>) &#123;<br>                list.add(i);<br>                pd[i] = <span class="hljs-keyword">true</span>;<br>            &#125;<br>            <span class="hljs-keyword">else</span> &#123;<br>                <span class="hljs-keyword">if</span> (cross(trees[list.get(list.size() - <span class="hljs-number">2</span>)], trees[list.get(list.size() - <span class="hljs-number">1</span>)], trees[i]) &gt; <span class="hljs-number">0</span>) &#123;<br>                    pd[list.get(list.size() - <span class="hljs-number">1</span>)] = <span class="hljs-keyword">false</span>;<br>                    list.remove(list.size() - <span class="hljs-number">1</span>);<br>                    pd[i] = <span class="hljs-keyword">true</span>;<br>                    list.add(i);<br>                    <span class="hljs-comment">//替换节点后一定要判断</span><br>                    <span class="hljs-keyword">while</span> (list.size() &gt; <span class="hljs-number">2</span> &amp;&amp; cross(trees[list.get(list.size() - <span class="hljs-number">3</span>)], trees[list.get(list.size() - <span class="hljs-number">2</span>)], trees[i]) &gt; <span class="hljs-number">0</span>) &#123;<br>                        pd[list.get(list.size() - <span class="hljs-number">2</span>)] = <span class="hljs-keyword">false</span>;<br>                        list.remove(list.size() - <span class="hljs-number">2</span>);<br>                    &#125;<br>                &#125;<br>                <span class="hljs-keyword">else</span> &#123;<br>                    pd[i] = <span class="hljs-keyword">true</span>;<br>                    list.add(i);<br>                &#125;<br>            &#125;<br>        &#125;<br><br>        <span class="hljs-keyword">int</span> x = <span class="hljs-number">0</span>;<br>        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = trees.length - <span class="hljs-number">2</span>; i &gt; <span class="hljs-number">0</span>; --i) &#123;<br>            <span class="hljs-keyword">if</span> (!pd[i]) &#123;<br>                <span class="hljs-keyword">if</span> (x &lt; <span class="hljs-number">1</span>) &#123;<br>                    list.add(i);<br>                    ++x;<br>                    pd[i] = <span class="hljs-keyword">true</span>;<br>                &#125;<br>                <span class="hljs-keyword">else</span> &#123;<br>                    <span class="hljs-keyword">if</span> (cross(trees[list.get(list.size() - <span class="hljs-number">2</span>)], trees[list.get(list.size() - <span class="hljs-number">1</span>)], trees[i]) &gt; <span class="hljs-number">0</span>) &#123;<br>                        pd[list.get(list.size() - <span class="hljs-number">1</span>)] = <span class="hljs-keyword">false</span>;<br>                        list.remove(list.size() - <span class="hljs-number">1</span>);<br>                        pd[i] = <span class="hljs-keyword">true</span>;<br>                        list.add(i);<br>                        <span class="hljs-keyword">while</span> (list.size() &gt; <span class="hljs-number">2</span> &amp;&amp; cross(trees[list.get(list.size() - <span class="hljs-number">3</span>)], trees[list.get(list.size() - <span class="hljs-number">2</span>)], trees[i]) &gt; <span class="hljs-number">0</span>) &#123;<br>                            pd[list.get(list.size() - <span class="hljs-number">2</span>)] = <span class="hljs-keyword">false</span>;<br>                            list.remove(list.size() - <span class="hljs-number">2</span>);<br>                    &#125;<br>                    &#125;<br>                    <span class="hljs-keyword">else</span> &#123;<br>                        pd[i] = <span class="hljs-keyword">true</span>;<br>                        list.add(i);<br>                    &#125;<br>                &#125;<br>            &#125;<br>        &#125;<br>		<span class="hljs-comment">//最后要单独判断首节点</span><br>        <span class="hljs-keyword">while</span> (list.size() &gt; <span class="hljs-number">2</span> &amp;&amp; cross(trees[list.get(list.size() - <span class="hljs-number">2</span>)], trees[list.get(list.size() - <span class="hljs-number">1</span>)], trees[<span class="hljs-number">0</span>]) &gt; <span class="hljs-number">0</span>) &#123;<br>                            pd[list.get(list.size() - <span class="hljs-number">1</span>)] = <span class="hljs-keyword">false</span>;<br>                            list.remove(list.size() - <span class="hljs-number">1</span>);<br>                    &#125;<br><br>        <span class="hljs-keyword">int</span>[][] result = <span class="hljs-keyword">new</span> <span class="hljs-keyword">int</span>[list.size()][<span class="hljs-number">2</span>];<br>        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt; list.size(); ++i) &#123;<br>            result[i] = trees[list.get(i)];<br>        &#125;<br><br>        <span class="hljs-keyword">return</span> result;<br>    &#125;<br>&#125;<br></code></pre></div></td></tr></table></figure>

<hr>
<h4 id="LC668-乘法表中第k小的数-H"><a href="#LC668-乘法表中第k小的数-H" class="headerlink" title="LC668 乘法表中第k小的数 H"></a>LC668 乘法表中第k小的数 H</h4><p>描述：给定高度m 、宽度n 的一张 m * n的乘法表，以及正整数k，你需要返回表中第k 小的数字。</p>
<p>解：<strong>对该乘法表的值进行二分查找，而非下标。</strong>关键在于每次需要统计中间值前有多少个数，即有多少数比中间值小。</p>
<figure class="highlight java"><table><tr><td class="gutter hljs"><div class="hljs code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br></pre></div></td><td class="code"><div class="hljs code-wrapper"><pre><code class="hljs java"><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span> </span>&#123;<br>    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">findKthNumber</span><span class="hljs-params">(<span class="hljs-keyword">int</span> m, <span class="hljs-keyword">int</span> n, <span class="hljs-keyword">int</span> k)</span> </span>&#123;<br>        <span class="hljs-keyword">int</span> l = <span class="hljs-number">1</span>, r = m * n;<br>        <span class="hljs-keyword">while</span> (l &lt; r) &#123;<br>        	<span class="hljs-comment">//计算中间值</span><br>            <span class="hljs-keyword">int</span> mid = l + (r - l) / <span class="hljs-number">2</span>;<br>            <br>            <span class="hljs-comment">//mid / n 得出有多少完整的列</span><br>            <span class="hljs-comment">//* n 得出完整的列有多少个数</span><br>            <span class="hljs-keyword">int</span> count = mid / n * n;<br>            <br>            <span class="hljs-comment">//计算完整的列之后的非完整的列中每列有多少个数比中间值小</span><br>            <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = mid / n + <span class="hljs-number">1</span>; i &lt;= m; ++i) &#123;<br>                count += mid / i;<br>            &#125;<br>            <br>            <span class="hljs-comment">//注意此处不能加 =，否则会导致结果 + 1</span><br>            <span class="hljs-keyword">if</span> (count &lt; k) &#123;<br>                l = mid + <span class="hljs-number">1</span>;<br>            &#125; <span class="hljs-keyword">else</span> &#123;<br>                r = mid;<br>            &#125;<br>        &#125;<br>        <span class="hljs-keyword">return</span> l;<br>    &#125;<br>&#125;<br></code></pre></div></td></tr></table></figure>
            </div>
            <hr>
            <div>
              <div class="post-metas mb-3">
                
                  <div class="post-meta mr-3">
                    <i class="iconfont icon-category"></i>
                    
                      <a class="hover-with-bg" href="/categories/%E7%AE%97%E6%B3%95/">算法</a>
                    
                  </div>
                
                
                  <div class="post-meta">
                    <i class="iconfont icon-tags"></i>
                    
                      <a class="hover-with-bg" href="/tags/%E5%85%B6%E4%BB%96%E7%AE%97%E6%B3%95/">其他算法</a>
                    
                  </div>
                
              </div>
              
                <p class="note note-warning">
                  
                    本博客所有文章未经允许，严禁转载！
                  
                </p>
              
              
                <div class="post-prevnext">
                  <article class="post-prev col-6">
                    
                    
                      <a href="/2022/03/24/%E7%AE%97%E6%B3%95--%E5%9B%9E%E6%BA%AF/">
                        <i class="iconfont icon-arrowleft"></i>
                        <span class="hidden-mobile">算法---回溯</span>
                        <span class="visible-mobile">上一篇</span>
                      </a>
                    
                  </article>
                  <article class="post-next col-6">
                    
                    
                      <a href="/2022/03/21/%E7%AE%97%E6%B3%95--%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92/">
                        <span class="hidden-mobile">算法---动态规划</span>
                        <span class="visible-mobile">下一篇</span>
                        <i class="iconfont icon-arrowright"></i>
                      </a>
                    
                  </article>
                </div>
              
            </div>

            
          </article>
        </div>
      </div>
    </div>
    
      <div class="d-none d-lg-block col-lg-2 toc-container" id="toc-ctn">
        <div id="toc">
  <p class="toc-header"><i class="iconfont icon-list"></i>&nbsp;目录</p>
  <div class="toc-body" id="toc-body"></div>
</div>

      </div>
    
  </div>
</div>

<!-- Custom -->


    

    
      <a id="scroll-top-button" aria-label="TOP" href="#" role="button">
        <i class="iconfont icon-arrowup" aria-hidden="true"></i>
      </a>
    

    
      <div class="modal fade" id="modalSearch" tabindex="-1" role="dialog" aria-labelledby="ModalLabel"
     aria-hidden="true">
  <div class="modal-dialog modal-dialog-scrollable modal-lg" role="document">
    <div class="modal-content">
      <div class="modal-header text-center">
        <h4 class="modal-title w-100 font-weight-bold">搜索</h4>
        <button type="button" id="local-search-close" class="close" data-dismiss="modal" aria-label="Close">
          <span aria-hidden="true">&times;</span>
        </button>
      </div>
      <div class="modal-body mx-3">
        <div class="md-form mb-5">
          <input type="text" id="local-search-input" class="form-control validate">
          <label data-error="x" data-success="v"
                 for="local-search-input">关键词</label>
        </div>
        <div class="list-group" id="local-search-result"></div>
      </div>
    </div>
  </div>
</div>
    

    
  </main>

  <footer class="text-center mt-5 py-3">
  <div class="footer-content">
     CC <i class="iconfont icon-love"></i> XX
  </div>
  
  <div class="statistics">
    
    

    
      
        <!-- 不蒜子统计PV -->
        <span id="busuanzi_container_site_pv" style="display: none">
            总访问量 
            <span id="busuanzi_value_site_pv"></span>
             次
          </span>
      
      
        <!-- 不蒜子统计UV -->
        <span id="busuanzi_container_site_uv" style="display: none">
            总访客数 
            <span id="busuanzi_value_site_uv"></span>
             人
          </span>
      
    
  </div>


  

  
</footer>


  <!-- SCRIPTS -->
  
  <script  src="https://cdn.jsdelivr.net/npm/nprogress@0/nprogress.min.js" ></script>
  <link  rel="stylesheet" href="https://cdn.jsdelivr.net/npm/nprogress@0/nprogress.min.css" />

  <script>
    NProgress.configure({"showSpinner":false,"trickleSpeed":100})
    NProgress.start()
    window.addEventListener('load', function() {
      NProgress.done();
    })
  </script>


<script  src="https://cdn.jsdelivr.net/npm/jquery@3/dist/jquery.min.js" ></script>
<script  src="https://cdn.jsdelivr.net/npm/bootstrap@4/dist/js/bootstrap.min.js" ></script>
<script  src="/js/events.js" ></script>
<script  src="/js/plugins.js" ></script>

<!-- Plugins -->


  <script  src="/js/local-search.js" ></script>



  
    
      <script  src="/js/img-lazyload.js" ></script>
    
  



  



  
    <script  src="https://cdn.jsdelivr.net/npm/tocbot@4/dist/tocbot.min.js" ></script>
  
  
    <script  src="https://cdn.jsdelivr.net/npm/@fancyapps/fancybox@3/dist/jquery.fancybox.min.js" ></script>
  
  
    <script  src="https://cdn.jsdelivr.net/npm/anchor-js@4/anchor.min.js" ></script>
  
  
    <script defer src="https://cdn.jsdelivr.net/npm/clipboard@2/dist/clipboard.min.js" ></script>
  



  <script defer src="https://busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js" ></script>




  <script  src="https://cdn.jsdelivr.net/npm/typed.js@2/lib/typed.min.js" ></script>
  <script>
    (function (window, document) {
      var typing = Fluid.plugins.typing;
      var title = document.getElementById('subtitle').title;
      
        typing(title);
      
    })(window, document);
  </script>















<!-- 主题的启动项 保持在最底部 -->
<script  src="/js/boot.js" ></script>


</body>
</html>
